import java.util.Arrays;
import java.util.Random;

/**
 * 双路快速排序法:解决当元素重复时时间复杂度高的问题（对于等于标定点的元素，要想办法将它分到数组的两端）
 * arr[l+1...i-1]<=v            arr[j+1...r]>=v
 */
public enum QuickSort2Ways implements Sort {
    INSTANCE;

    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        Random random = new Random();
        sort(arr, 0, arr.length - 1, random);
    }

    private <E extends Comparable<E>> void sort(E[] arr, int l, int r, Random random) {
//        if (l >= r) return;
        if (l - r <= 15) {
            insertionSort(arr, l, r);
            return;
        }
        int p = partition(arr, l, r, random);
        sort(arr, l, p - 1, random);
        sort(arr, p + 1, r, random);
    }

    /**
     * @param arr
     * @param l
     * @param r
     * @param <E>
     * @return
     * @循环不变量 arr[l+1...j] `<` v;arr[j+1...i] &gt; v
     * @优化目标：生成一个[l,r]区间的随机值，（1.生成一个[0,r-l]区间的随机值），l+[0,r-l]区间的随机值——>[l,r]区间的随机值
     */
    private <E extends Comparable<E>> int partition(E[] arr, int l, int r, Random random) {
        //生成[l,r]之间的随机索引
        int p = random.nextInt(r - l + 1) + l;
        SortingHelper.INSTANCE.swap(arr, l, p);

        //arr[l+1...i-1]<=v;arr[j+1...r]>=v
        int i = l + 1, j = r;
        while (true) {
            while (i <= j && arr[i].compareTo(arr[l]) < 0) i++;
            while (i <= j && arr[j].compareTo(arr[l]) > 0) j--;

            if (i >= j) break;
            SortingHelper.INSTANCE.swap(arr, i, j);
            i++;
            j--;
        }
        SortingHelper.INSTANCE.swap(arr, l, j);
        return j;
    }

    /**
     * @param arr
     * @param l
     * @param r
     * @param <E>
     */
    public <E extends Comparable<E>> void insertionSort(E[] arr, int l, int r) {
        for (int i = l; i <= r; i++) {
            E t = arr[i];
            int j;
            for (j = i; j - 1 >= l && t.compareTo(arr[j - 1]) < 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = t;
        }
    }

    private <E extends Comparable<E>> void printArr(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(",");
            }
        }
    }


    public static void main(String[] args) {
        int n = 100000;

        Integer[] arr = ArrayGenerator.INSTANCE.generatorRandomArray(n, n);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);

        System.out.println("Random Array");
        SortingHelper.INSTANCE.sortTest(QuickSort3.INSTANCE, arr);
        SortingHelper.INSTANCE.sortTest(QuickSort2Ways.INSTANCE, arr2);
        System.out.println();

        arr = ArrayGenerator.INSTANCE.generatorRandomArray(n, n);
        arr2 = Arrays.copyOf(arr, arr.length);

        System.out.println("Ordered Array");
        SortingHelper.INSTANCE.sortTest(QuickSort3.INSTANCE, arr);
        SortingHelper.INSTANCE.sortTest(QuickSort2Ways.INSTANCE, arr2);
        System.out.println();

        System.out.println("Same Value Array");
        arr = ArrayGenerator.INSTANCE.generatorRandomArray(n, 1);
        arr2 = Arrays.copyOf(arr, arr.length);
        SortingHelper.INSTANCE.sortTest(QuickSort3.INSTANCE, arr);
        SortingHelper.INSTANCE.sortTest(QuickSort2Ways.INSTANCE, arr2);
        System.out.println();
    }
}
